\documentclass[a4paper,10pt]{article}
\usepackage[utf8]{inputenc}
\usepackage{amssymb,amsmath}
\usepackage{graphicx}
\usepackage[linesnumbered]{algorithm2e}
\usepackage{float}
\usepackage[brazil]{babel}



\mathchardef\mhyphen="2D

\title{MAC5789\\
Laboratório de Inteligência Artificial\\
Projeto 4 - Planejamento Probabilístico\\
Profa. Leliane Nunes de Barros}
\author{Renato Urquiza Lundberg}

\begin{document}

\maketitle


\pagebreak

\section{Introdução}

Este relatório descreve brevemente os resultados obtidos na realização dos
experimentos propostos para o quarto projeto da disciplina.

O projeto consiste na implementação e comparação de algoritmos de planejamento
probabilístico.

O modelo de mundo analisado possui finitos estados discretos e um conjunto de
ações, juntamente com a probabilidade de seus efeitos: mundo é completamente
observável.

Os algoritmos propostos foram o Value Iteration (VI), Real Time Dynamic
Programming (RTDP) e opcionalmente o Labeled Real Time Dynamic Programming
(LRTDP). Este relatório irá tratar apenas dos dois primeiros.

\pagebreak

\section{Desenvolvimento}

O desenvolvimento se deu como nos demais projetos da disciplina, tendo foco na
implementação de partes facilmente testáveis que iriam compor o todo.

Inicialmente foi modelado o mundo, com todas as suas propriedades e facilidades
de construção declarativa, facilitando a construção posterior de testes dos
algoritmos implementados sem depender de arquivos de entrada.

Em seguida foram construídos os algoritmos VI e RTDP. Para fins de testes foi
criado um cenário baseado em um ponto inicial e um final com dois caminhos
possíveis e pontos intermediários, sendo que o primeiro trecho indicava que um
caminho era mais vantajoso, mas posteriormente o algoritmo deveria ver que o
outro é melhor.

Como ambos os algoritmos utilizam o Bellman Backup, este conceito foi extraído e
reutilizado entre as implementações. O algoritmo VI basicamente executa
melhorias do Bellman Backup, sempre melhorando todos os estados. Já o algoritmo
RTDP utiliza o Bellman Backup apenas sobre estados visitados durante
explorações.

\pagebreak

\section{Experimentos}

\subsection{Medições}

Para cada cenário executado foram gravados os seguintes valores: número de
estados, tempo de execução do algoritmo VI, número de iterações do algoritmo VI,
tempo de execução do algoritmo RTDP, número de iterações do algoritmo RTDP,
tamanho da política gerada pelo RTDP e número de divergências entre as
políticas.

O tempo é medido utilizando o melhor relógio disponível na máquina, e o
resultado apresentado em segundos, com decimais até a casa dos milisegundos.

\subsection{Cenários fornecidos}

Os seguintes resultados foram obtidos com os cenários fornecido no site
da disciplina:

\begin{verbatim}
States:                             11
VI Time:                        20.800
VI Iteractions:                     13
RTDP Time:                      20.062
RTDP Iteractions:                   15
RTDP Policy Size:                    8
Policy Divergencies:                 0

States:                            176
VI Time:                       196.275
VI Iteractions:                     35
RTDP Time:                      92.814
RTDP Iteractions:                   53
RTDP Policy Size:                  175
Policy Divergencies:                 0

States:                            541
VI Time:                       133.240
VI Iteractions:                     60
RTDP Time:                     191.416
RTDP Iteractions:                  126
RTDP Policy Size:                  540
Policy Divergencies:                 0

States:                           1106
VI Time:                       377.432
VI Iteractions:                     85
RTDP Time:                     633.261
RTDP Iteractions:                  234
RTDP Policy Size:                 1105
Policy Divergencies:                 0

States:                           1871
VI Time:                       993.414
VI Iteractions:                    110
RTDP Time:                    1717.788
RTDP Iteractions:                  324
RTDP Policy Size:                 1870
Policy Divergencies:                 0

States:                           2836
VI Time:                      1521.986
VI Iteractions:                    135
RTDP Time:                    4743.486
RTDP Iteractions:                  497
RTDP Policy Size:                 2835
Policy Divergencies:                 0

States:                           4001
VI Time:                      2225.864
VI Iteractions:                    160
RTDP Time:                    3972.596
RTDP Iteractions:                  316
RTDP Policy Size:                 4000
Policy Divergencies:                 1

States:                           5366
VI Time:                      4335.287
VI Iteractions:                    185
RTDP Time:                    6777.449
RTDP Iteractions:                  348
RTDP Policy Size:                 5365
Policy Divergencies:                 1

States:                           6931
VI Time:                      6137.639
VI Iteractions:                    211
RTDP Time:                   23717.398
RTDP Iteractions:                 1000
RTDP Policy Size:                 6915
Policy Divergencies:               793

States:                           8696
VI Time:                      9506.902
VI Iteractions:                    236
RTDP Time:                   18909.557
RTDP Iteractions:                  541
RTDP Policy Size:                 8695
Policy Divergencies:                 2

States:                          10661
VI Time:                     13141.342
VI Iteractions:                    261
RTDP Time:                   24019.941
RTDP Iteractions:                  572
RTDP Policy Size:                10660
Policy Divergencies:                 3
\end{verbatim}

Como podemos ver, o algoritmo O RTDP não foi nada bem nos testes. Para casos
pequenos o resultado foi até competitivo, mas o tempo de execução do algoritmo
cresceu muito mais rapidamente do que o tempo do VI. 

Vale a pena notar que a política gerada pelo RTDP é completa para estes
cenários, e o número de divergências encontradas foi muito baixa.

\begin{figure}[H]
\begin{center}
 \includegraphics[scale=0.5]{tempoVIxRTDP.png}
\end{center}
\end{figure}

O gráfico acima ilustra comportamento do tempo de execução, deixando claro o
comportamento errático do tempo de execução do RTDP.



\subsection{Alterando fator de desconto}

Como sugerido, foram feitos testes com o fator de desconto alterado.
Originalmente os arquivos de entrada determinam que o fator de desconto seja 1.

Os resultados abaixo foram obtidos utilizando fator de desconto 0.95.

\begin{verbatim}
States:                             11
VI Time:                        24.146
VI Iteractions:                     16
RTDP Time:                      15.810
RTDP Iteractions:                   17
RTDP Policy Size:                    8
Policy Divergencies:                 0

States:                            176
VI Time:                        92.271
VI Iteractions:                     27
RTDP Time:                      57.729
RTDP Iteractions:                   40
RTDP Policy Size:                  175
Policy Divergencies:                 0

States:                            541
VI Time:                        59.844
VI Iteractions:                     29
RTDP Time:                     157.892
RTDP Iteractions:                   69
RTDP Policy Size:                  532
Policy Divergencies:               160

States:                           1106
VI Time:                       152.374
VI Iteractions:                     29
RTDP Time:                     314.087
RTDP Iteractions:                   82
RTDP Policy Size:                 1072
Policy Divergencies:               610

States:                           1871
VI Time:                       263.407
VI Iteractions:                     29
RTDP Time:                     527.018
RTDP Iteractions:                   99
RTDP Policy Size:                 1849
Policy Divergencies:              1191

States:                           2836
VI Time:                       421.279
VI Iteractions:                     29
RTDP Time:                    1489.163
RTDP Iteractions:                  152
RTDP Policy Size:                 2687
Policy Divergencies:              2217

States:                           4001
VI Time:                       591.886
VI Iteractions:                     29
RTDP Time:                    6848.757
RTDP Iteractions:                  532
RTDP Policy Size:                 4000
Policy Divergencies:              1384

States:                           5366
VI Time:                       823.279
VI Iteractions:                     29
RTDP Time:                    3824.618
RTDP Iteractions:                  201
RTDP Policy Size:                 4895
Policy Divergencies:              3346

States:                           6931
VI Time:                      1076.475
VI Iteractions:                     29
RTDP Time:                   24544.986
RTDP Iteractions:                  994
RTDP Policy Size:                 6930
Policy Divergencies:              3213

States:                           8696
VI Time:                      1076.064
VI Iteractions:                     29
RTDP Time:                    6327.982
RTDP Iteractions:                  221
RTDP Policy Size:                 8467
Policy Divergencies:              7424

States:                          10661
VI Time:                      1509.917
VI Iteractions:                     29
RTDP Time:                    9966.420
RTDP Iteractions:                  252
RTDP Policy Size:                10503
Policy Divergencies:              8689
\end{verbatim}

Ambos os algoritmos tiveram tempo de execução muito reduzido, quando comparado
com o tempo de execução com fator de desconto 1.0.

A tendência de tempo de execução maior para o RTDP se manteve.

O número de divergências entre as políticas geradas pelos algoritmos para os
mesmos cenários foi bastante elevado, e a política do RTDP excluiu alguns
estados.

\pagebreak

\section{Conclusão}

Os resultados pareceram inesperados em um primeiro momento, pois é natural que
um algoritmo mais esperto como o RTDP seja mais eficiente, ignorando estados
absurdos.

Olhando mais atentamente para a estratégia do RTDP, entretanto, vemos que ela só
funciona caso seja possível descartar estados. Um estado é ignorado basicamente
em duas condições:

\begin{enumerate}
 \item Se é desconectado do estado inicial.
 \item Se a heurística o torna desinteressante.
\end{enumerate}

Os problemas testados utilizam um grafo conexo, portanto a primeira condição não
será atendida, restando a heurística. Como foi utilizada a heurística trivial,
considerar todos os estados como zero, o algoritmo foi obrigado a considerar
todos os estados, após diversas etapas de exploração.

Enquanto o algoritmo VI já partia considerando todos os estados, o algoritmo 
RTDP levava até centenas de rodadas para descobrir que todos os estados deveriam
ser considerados para só então calculá-los ao longo de algumas iterações. No
final o RTDP estava levando em conta os mesmos nós que o VI, chegando em 
resultados quase idênticos, com poucas divergências.

Como a maioria dos algoritmos que levam em conta a eficiência em determinados
cenários e dependentes de heurísticas, o desempenho do RTDP nos cenários
testados foi ruim.



\end{document}